package ren.kane.phoenix.util.tree;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * 树的构建类.
 *
 * @author renrk(1275) on 2019-03-01 9:43 AM
 **/
public class TreeBuilder {

    /**
     * 根据列表递归构造树.
     * Created by renrk on 3/1/2019 11:03 AM
     */
    public static <T extends TreeNode<T>> List<T> listToTree(List<T> treeNodeList, String parentId, String breadCrumb) {
        List<T> treeNodes = new ArrayList<>();
        if (null != treeNodeList) {
            List<T> parentList = new ArrayList<>();
            List<T> childList = new ArrayList<>();
            // 遍历，找出所有的父节点和子节点
            for (T treeNode : treeNodeList) {
                // 是否根节点
                treeNode.setRootNode(null == treeNode.getParentId());
                // 根节点或者非根节点的父节点
                if (null == treeNode.getParentId() || treeNode.getParentId().equals(parentId)) {
                    parentList.add(treeNode);
                } else {
                    childList.add(treeNode);
                }
            }
            // 遍历父节点
            for (T treeNode : parentList) {
                // 面包屑路径
                treeNode.setBreadCrumb(breadCrumb.isEmpty() ? treeNode.getId() : breadCrumb.concat("/").concat(treeNode.getId()));
                // 递归，获取父节点所有的子节点
                List<T> children = listToTree(childList, treeNode.getId(), treeNode.getBreadCrumb());
                // 是否叶子节点，叶子节点的id要加入所有下级叶子节点id集合
                if (children.isEmpty()) {
                    treeNode.setLeafNode(true);
                    treeNode.getLeafNodeIds().add(treeNode.getId());
                }
                treeNode.setChildren(children);
                // 遍历所有子节点
                for (T child : children) {
                    // 添加下级节点id和所有下级节点的id集合
                    treeNode.getJuniorIds().add(child.getId());
                    treeNode.getJuniorIds().addAll(child.getJuniorIds());
                    // 添加所有下级叶子节点id集合
                    treeNode.getLeafNodeIds().addAll(child.getLeafNodeIds());
                }
                treeNodes.add(treeNode);
            }
        }
        return treeNodes;
    }

    /**
     * 处理无统一根节点的列表，转化成树的集合.
     * Created by renrk on 3/1/2019 11:03 AM
     */
    public static <T extends TreeNode<T>> List<T> listToTree(List<T> treeNodeList) {
        Set<String> parentIdSet = new HashSet<>();
        // 遍历，全部置为根节点
        for (T treeNode : treeNodeList) {
            parentIdSet.add(treeNode.getParentId());
            treeNode.setRootNode(true);
        }
        // 遍历，找出不是根节点的
        for (T treeNode1 : treeNodeList) {
            for (T treeNode2 : treeNodeList) {
                if (null == treeNode2.getParentId()) {
                    continue;
                }
                if (treeNode2.isRootNode() && !treeNode2.getId().equals(treeNode1.getId())
                    && treeNode2.getParentId().equals(treeNode1.getId())) {
                    parentIdSet.remove(treeNode2.getParentId());
                    treeNode2.setRootNode(false);
                }
            }
        }
        // 遍历根节点id，递归构造树，获得树集合
        Set<T> treeNodeSet = new HashSet<>();
        for (String parentId : parentIdSet) {
            List<T> treeNodes = new ArrayList<>(treeNodeList);
            treeNodes = listToTree(treeNodes, parentId, "");
            treeNodeSet.addAll(treeNodes);
        }
        return new ArrayList<>(treeNodeSet);
    }

    public static void main(String[] args) {
        String test1 = "[{\"id\":\"1\",\"parentId\":null},{\"id\":\"2\",\"parentId\":\"3\"},{\"id\":\"3\",\"parentId\":\"1\"},{\"id\":\"4\",\"parentId\":\"3\"},{\"id\":\"5\",\"parentId\":\"7\"},{\"id\":\"6\",\"parentId\":null},{\"id\":\"7\",\"parentId\":\"null\"},{\"id\":\"8\",\"parentId\":\"0\"},{\"id\":\"9\",\"parentId\":\"5\"},{\"id\":\"10\",\"parentId\":\"8\"}]";
        String test2 = "[{\"id\":\"2\",\"parentId\":\"3\"},{\"id\":\"3\",\"parentId\":\"1\"},{\"id\":\"4\",\"parentId\":\"3\"},{\"id\":\"5\",\"parentId\":\"7\"},{\"id\":\"6\",\"parentId\":null},{\"id\":\"7\",\"parentId\":\"null\"},{\"id\":\"8\",\"parentId\":\"0\"},{\"id\":\"9\",\"parentId\":\"5\"},{\"id\":\"10\",\"parentId\":\"8\"}]";
        List<TreeNode> treeNodeList = JSON.parseArray(test1, TreeNode.class);
        List<TreeNode> list1 = listToTree(treeNodeList, null, "");
        List<TreeNode> list2 = listToTree(treeNodeList);
        System.out.println(list2);
    }
}
